The present invention relates to a multiprocessor system having a mutual exclusion control function.
With recent development in LSI technology, it is proposed to construct a multiprocessor system of highly enhanced performance. A multiprocessor system can be constructed by a plurality of processors each having a different function such as general arithmetic operation function or an input/output data processing function. The kinds and the number of processors constituting a multiprocessor system are increasing in order to improve the data processing performance of the system. Each processor must have a mutual exclusion control function for performing operation correctly. A processor having a mutual exclusion control function in a multiprocessor system can execute a sequence of operation steps without being interfered by any other processors.
FIG. 1 shows a multiprocessor system having processors 1 and 2 which commonly use a memory device 3. Assume that the processor 1 transfers data to the processor 2 through a queue or queuing area 4 in the memory device 3. In order to inform the processor 2 of the number of data transferred to the memory device 3, the processor 1 increases the content of a specific memory area 5 in the memory device 3 by one count every time it transfers data to the queuing area 4. The processor 2 detects the number of data transferred by the processor 1 to the queuing area 4 by reading the content of the specific memory area 5. The processor 2 decreases the content of the specific memory area 5 by one count every time it fetches data stored in the queuing area 4 thereinto. As a result, the content stored in the specific memory area 5 indicates the number of data which has been transferred by the processor 1 but which has not been fetched into the processor 2.
A series of steps to be described below must be executed to allow the processor 1 to increment the content of the specific memory area 5 by "1".
STEP 1: To read out the content of the specific memory area 5 PA0 STEP 2: To add "1" to the content read out from the specific memory area 5 PA0 STEP 3: To write the sum or addition result obtained in STEP 2 in the specific memory area 5. PA0 STEP 4: To read out the content of the specific memory area 5 PA0 STEP 5: To subtract "1" from the content read out from the specific memory area 5 PA0 STEP 6: To write the difference or subtraction result obtained in STEP 5 in the specific memory area 5.
On the other hand, a series of steps to be described below must be executed to allow the processor 2 to decrement the content of the specific memory area 5 by "1".
A case will now be described where the processors 1 and 2 simultaneously start executing series of steps described above. If the processor 2 starts executing STEP 4 immediately before the processor 1 executes STEP 3 after having completed STEPs 1 and 2, the content written into the specific memory area 5 after STEP 6 is completed is equal to the value obtained by subtracting "1" from the content stored in the specific memory area 5 before STEP 1. On the other hand, if the processor 1 starts executing STEP 1 immediately before the processor 2 executes STEP 6 after having completed STEPs 4 and 5, the content written into the specific memory area 5 after STEP 3 is completed is equal to the value obtained by adding "1" to the content stored in the specific memory area 5 before STEP 4. In this manner, if the processors 1 and 2 execute the series of STEPs 1 to 3 and the series of STEPs 4 to 6 almost simultaneously, the content stored in the specific memory area 5 after those series of steps are completed differs from that before they are executed. Since, in this case, the processor 1 adds "1" to the content of the specific memory area 5 and the processor 2 substracts "1" from the contents of the specific memory 5, the content stored in the specific memory area 5 after the series of steps are completed should be equal to that before the series of steps are started. Such an error is caused since neither of the processors 1 and 2 can execute the series of steps exclusively.
In view of this problem, it is conventionally proposed to realize a mutual exclusion control function by allowing a plurality of processors 6-1 to 6-N commonly connected to the memory device 3, as shown in FIG. 2, to execute a test-and-set instruction. The test-and-set instruction allows exclusive execution of a step to read out the content of a flag memory area 7 in the memory device 3 and a step to write specific data (e.g., data "1") into the flag memory area 7.
When a processor executes a queuing operation by using the test-and-set instruction, it first executes the test-and-set instruction for the flag memory area 7 in the memory device 3. If the processor detects that data "1" is set in the flag memory area 7, it waits until the content of the memory flag area becomes "0". When the processor detects that data "0" is set in the flag memory area 7, it executes a sequence of the queuing steps. Simultaneously, it keeps the content of the flag memory area 7 set to "1" during the period of the execution of the queuing operation in order to prevent another processor from carrying out a queuing operation. When the queuing operation is completed, the processor sets the content of the flag memory area 7 to "0". This enables another queuing operation to follow.
However, in a multiprocessor system shown in FIG. 2, since the flag memory area 7 is provided in the memory device 3, the memory device 3 must be accessed in order for the processor to check the content of the flag memory area 7. Especially when the content of the flag memory area 7 is "1", one or more processors which want to execute the subsequent queuing operation access the memory device 3 repeatedly until the content of the flag memory area 7 is set to "0". This degrades the performance of the multiprocessor system extremely.
In order to reduce the frequency of access to the memory device 3, the use of a mutual exclusion control device 9 as shown in FIG. 3 is proposed. The mutual exclusion control device 9 is provided separately from the memory device 3 and consists of, for example, a group of registers for storing flags. By utilizing the mutual exclusion control device 9, the memory device 3 need not be accessed every time the content of the flag is checked. However, if the mutual exclusion control device 9 operates erroneously, it may adversely affect the operation of the multiprocessor system. For example, when a flag of the mutual exclusion control device 9 is reset by a noise while the processor 6-1 is executing the queuing operation, one or more of the other processors may start executing another queuing operation. In addition, if data "1" is set in the flag by a noise before any one of processors 6-1 to 6-N executes the test-and-set instruction for the flag, queuing operations by the processors are prohibited eternally. In order to solve this problem, the mutual exclusion control device 9 must operate with high reliability. This results in higher cost of the mutual exclusion control device. Furthermore, the mutual exclusion control device must have extra connecting ports for allowing more processors to be connected. However, since it is practically impossible to increase the number of processors exceeding the number of the connecting ports, the number of processors in a multiprocessor system is limited.